#include "BTree.h"

BTree::~BTree()
{
	if( Root )
	{
		//recursive delete // FreeAllElements
		FreeAllElements();
		Root = NULL;
	}
}

TreeItem* BTree::Find(int k)
{
	int tempKey;
	TreeNode* temp = new TreeNode;
	TreeItem *LTreeItem;


	if(!Root)
		return NULL;
	temp=Root;
	while(!temp->isLeaf())
	{
		if( k < temp->GetMinM() )
		{
			temp=temp->GetLeft();
			continue;
		}
		if( !temp->GetRight() || ( k < temp->GetMinR() && temp->GetRight() ) )
		{
			temp=temp->GetMid();
			continue;
		}
		temp=temp->GetRight();
	}

	if(temp) 
	{
		LTreeItem = temp->GetData();
		tempKey = LTreeItem->getKey();
		if( k == tempKey )
			return temp->GetData();
		else
			return(NULL);
	}
	else return NULL;
}

int BTree::IsEmpty()
{
	if(!Root) 
		return 1;
	
	return 0;	
}

TreeNode* BTree::find_node_parent(TreeNode* node) 
{
		TreeNode* curr = Root;

		while( !( curr->isLeaf() )  )  
		{
			if( curr->GetMinM() > node->GetMinM() )
				curr = curr->GetLeft();
			else 
			{
				if( !curr->GetRight() )
					curr = curr->GetMid();
				else
				{
					if( curr->GetMinM() < node->GetMinM() && curr->GetMinR() > node->GetMinM() ) 
						curr = curr->GetMid();
					else
						curr = curr->GetRight();
				}
			}
		}
		return curr->getParent();
}

void BTree:: basic_Insert(TreeNode* node)
{
	if(NumOfLeaf == 0)
	{
		Root = new TreeNode(0,"");
		Root->SetData(node->GetData());
		//Root->SetData(node->GetData()->getKey(),node->GetData()->getData());
		Root->SetMinM(node->GetData()->getKey()); 
		Root->setMinHolder(node->GetData()->getKey());
		return;
	}
	
	if(NumOfLeaf == 1)
	{
		TreeNode* newRoot = new TreeNode;

		node->SetMinM(node->GetData()->getKey());
		node->setMinHolder(node->GetData()->getKey());
	
		if( Root->getMinHolder() < node->getMinHolder() )
		{
			newRoot->SetLeft(Root);
			newRoot->SetMid(node);
			newRoot->setMinHolder(Root->getMinHolder());
			newRoot->SetMinM( node->getMinHolder() );	
		}
		else
		{
			newRoot->SetLeft(node);
			newRoot->SetMid(Root);
			newRoot->setMinHolder(node->getMinHolder());
			newRoot->SetMinM( Root->getMinHolder() );
		}

		newRoot->setNumOfChildren(2);
		node->setParent( newRoot );
		Root->setParent( newRoot );
		Root = newRoot;
		return;
	}

	if(NumOfLeaf == 2)
	{
		node->setMinHolder(node->GetData()->getKey());
		node->SetMinM(node->GetData()->getKey());
		
		TreeNode *ParentNode = find_node_parent(node);	

		insert_child_to_parent(node,ParentNode);
		ParentNode->SetMinM(ParentNode->GetMid()->getMinHolder());
		ParentNode->SetMinR(ParentNode->GetRight()->getMinHolder());
		ParentNode->setNumOfChildren(3);
		return;
	}
}

void BTree:: Insert_Helper(TreeNode* node)
{
	if(NumOfLeaf <= 2)
	{
		basic_Insert( node );
	}

	if(NumOfLeaf > 2)
	{
		node->setMinHolder(node->GetData()->getKey());
		node->SetMinM(node->GetData()->getKey());
		TreeNode *ParentNode = find_node_parent(node);	
		add_node(node, ParentNode);
	}
	NumOfLeaf++;
}

void BTree::add_node(TreeNode *node,TreeNode *Parent)
{
	if(Parent->getNumOfChildren() == 3)
	{
		TreeNode *NewNode=new TreeNode;
		Split(NewNode,node,Parent);

		if ( Parent->getParent() == NULL) // the parent is a child of the root
		{
			TreeNode *NewRoot=new TreeNode;
			if( Parent->GetMinM() > NewNode->GetMinM() )
			{
				NewRoot->SetLeft(NewNode);
				NewRoot->SetMid(Parent);
				NewRoot->GetLeft()->setParent(NewRoot);
				NewRoot->GetMid()->setParent(NewRoot);
			}
			else
			{
				NewRoot->SetLeft(Parent);
				NewRoot->SetMid(NewNode);
				NewRoot->GetLeft()->setParent(NewRoot);
				NewRoot->GetMid()->setParent(NewRoot);

			}

			Root=NewRoot;
			Root->setMinHolder(Root->GetLeft()->getMinHolder());
			Root->setNumOfChildren(2);
			Root->SetMinM(Root->GetMid()->getMinHolder());
			Parent->setParent(Root);
			NewNode->setParent(Root);
		}
		else
			add_node(NewNode,Parent->getParent());
	}
	else
	{
		insert_child_to_parent( node , Parent );
		Parent->SetMinM( Parent->GetMid()->GetMinM() );		
		Parent->SetMinR( Parent->GetRight()->GetMinM() );
		Parent->setNumOfChildren(3);
	}
}

void BTree::insert_child_to_parent(TreeNode* node , TreeNode* Parent)
{
	TreeNode *temp1,*temp2,*temp3;
	temp1=Parent->GetLeft();
	temp2=Parent->GetMid();
	temp3=node;

	node->setParent(Parent);
	Parent->SetLeft( find_min(temp1,temp2,node));
	Parent->SetMid( find_mid(temp1,temp2,node));
	Parent->SetRight( find_max(temp1,temp2,node));
	Parent->setMinHolder(Parent->GetLeft()->getMinHolder());
}

void BTree::Split(TreeNode* uncale , TreeNode *node , TreeNode *Parent)
{
	if( Parent->GetLeft()->GetMinM() > node->GetMinM() )
	{
		uncale->SetLeft(node);
		uncale->SetMid(Parent->GetLeft());
		Parent->SetLeft(Parent->GetMid());
		Parent->SetMid(Parent->GetRight());
		node->setParent(uncale);
		uncale->GetMid()->setParent(uncale);
	}
	
	if( (Parent->GetLeft()->GetMinM() < node->GetMinM() ) && ( node->GetMinM() < Parent->GetMinM() ) )
	{
		uncale->SetLeft(Parent->GetLeft());
		uncale->SetMid(node);
		Parent->SetLeft(Parent->GetMid());
		Parent->SetMid(Parent->GetRight());
		node->setParent(uncale);
		uncale->GetLeft()->setParent(uncale);
	}
	
	if( (Parent->GetLeft()->GetMinM() < node->GetMinM() ) && ( node->GetMinM() < Parent->GetMinR() ) )
	{
		uncale->SetLeft(Parent->GetLeft());
		uncale->SetMid(Parent->GetMid());
		Parent->SetLeft(node);
		Parent->SetMid(Parent->GetRight());
		node->setParent(Parent);
		uncale->GetLeft()->setParent(uncale);
		uncale->GetMid()->setParent(uncale);

	}
	
	if( Parent->GetRight()->GetMinM() < node->GetMinM() )
	{
		uncale->SetLeft(Parent->GetLeft());
		uncale->SetMid(Parent->GetMid());
		Parent->SetLeft(Parent->GetRight());
		Parent->SetMid(node);
		node->setParent(Parent);
		uncale->GetLeft()->setParent(uncale);
		uncale->GetMid()->setParent(uncale);
	}
	Parent->SetRight(NULL);
	Parent->SetMinR(NULL);
		
	Parent->setNumOfChildren(Parent->getNumOfChildren()-1);
	uncale->setNumOfChildren(2);
	uncale->SetMinM(uncale->GetMid()->getMinHolder());
	Parent->SetMinM(Parent->GetMid()->getMinHolder());
	uncale->setMinHolder(uncale->GetLeft()->getMinHolder());
	Parent->setMinHolder(Parent->GetLeft()->getMinHolder());
}

TreeNode* BTree::find_min(TreeNode* node1,TreeNode* node2,TreeNode* node3)
{
	int key1,key2,key3;

	key1=node1->getMinHolder();
	key2= node2->getMinHolder();
	key3= node3->getMinHolder();

	if( ( key1 < key2 ) && ( key1 < key3 ) )
		return node1;

	if( ( key2 < key1 ) && ( key2 < key3 ) )
		return node2;

	return node3;
}

TreeNode * BTree::find_mid(TreeNode* node1,TreeNode* node2,TreeNode* node3)
{
	int key1,key2,key3;

	key1 = node1->getMinHolder();
	key2 = node2->getMinHolder();
	key3 = node3->getMinHolder();

	if( ((key1 < key2) && (key1 > key3)) || ((key1 < key3) && (key1 > key2)) )
		return node1;

	if( ((key2 < key1) && (key2 > key3)) || ((key2 < key3) && (key2 > key1)) ) 
		return node2;

	return node3;
}

TreeNode* BTree:: find_max(TreeNode* node1,TreeNode* node2,TreeNode* node3)
{
	int key1,key2,key3;

	key1=node1->getMinHolder();
	key2= node2->getMinHolder();
	key3= node3->getMinHolder();

	if( ( key1 > key2 ) && ( key1 > key3 ) )
		return node1;

	if( ( key2 > key1 ) && ( key2 > key3 ) )
		return node2;

	return node3;
}

int BTree:: Insert(int k,string d)
{
	TreeNode *node= new TreeNode(k,d); // using 2nd constactor
	TreeItem *temp;

	temp = Find(k);

	// no such worker
	if(!temp) 
	{
		Insert_Helper(node);
		return 1;
	}
	else
		return 0;

}

void BTree::PrintBTree(TreeNode* node)
{
	if(node)
	{
		this->PrintBTree(node->GetLeft());
		this->PrintBTree(node->GetMid());
		this->PrintBTree(node->GetRight());
		node->Print();
	}
}

//void BTree:: PrintBTree()
//{
//	//if (Root==NULL || NumOfLeaf==0)
//	//	outPutFile<< "Empty" << endl;
//	//else
//		//this->SaveInFile(outPutFile,Root);
//}

//void BTree:: SaveInFile (ofstream &out_file,TreeNode* node)
//{
//	/*if(node)
//	{
//		this->SaveInFile(out_file,node->GetLeft());
//		this->SaveInFile(out_file,node->GetMid());
//		this->SaveInFile(out_file,node->GetRight());
//		node->SaveInFile( out_file);	
//	}*/
//
//}

void BTree :: FreeAllElements()
{
	if( !Root->getParent() )
	{
		NumOfLeaf=0;
		if(Root->GetRight() )
		{
			delete( Root->GetRight()->GetData() );
			Root->GetRight()->setParent(NULL);			
			delete( Root->GetRight() );
			Root->SetRight(NULL);
		}
		if(Root->GetMid() )
		{
			delete( Root->GetMid()->GetData() );
			Root->GetMid()->setParent(NULL);		
			delete( Root->GetMid() );
			Root->SetMid(NULL);
		}
		if(Root->GetLeft() )
		{
			delete( Root->GetLeft()->GetData() );
			Root->GetLeft()->setParent(NULL);			
			delete( Root->GetLeft() );
			Root->SetLeft(NULL);
		}
		
		delete Root;
		Root = NULL;
		return;
	}
	else
	{
		Root = Root->GetLeft();
		FreeAllElements();
		Root = Root->GetMid();
		FreeAllElements();
		Root = Root->GetRight();
		FreeAllElements();
	}
}

//1.left//2.middle//3.right
int BTree::Son_Location(TreeNode* Parent,TreeNode* node)
{
	if( Parent->GetLeft() == node )
		return 1;

	if( Parent->GetMid() == node )
		return 2;

	return 3;
}

TreeItem *BTree::Delete(int k)
{
	TreeNode* node;
	TreeItem *temp;

	if ( NumOfLeaf == 0 )
		return NULL;
	node = findKey(k);

	if ( !node)
		return NULL;
	else
	{
		temp = node->GetData();
		
		if( NumOfLeaf == 1 )
		{
			Root = NULL;
			NumOfLeaf = 0;
			return temp;
		}
		//the root is what remains
		if( NumOfLeaf == 2 )
		{
			NumOfLeaf = 1;
			if( temp->getKey() == Root->GetLeft()->GetData()->getKey() )
				Root = Root->GetMid();
			else
				Root = Root->GetLeft();

			return temp;
		}
		if( NumOfLeaf == 3 )
		{
			NumOfLeaf = 2;
			if( temp->getKey() == Root->GetLeft()->GetData()->getKey() )
			{
				Root->SetLeft( Root->GetMid() );
				Root->SetMid( Root->GetRight() );
			}
			if( temp->getKey() == Root->GetMid()->GetData()->getKey() )
			{
				Root->SetMid( Root->GetRight() );
			}
			Root->SetMinM(Root->GetLeft()->getMinHolder() );
			Root->SetMinR(NULL);
			Root->setMinHolder( Root->GetLeft()->getMinHolder() );
			Root->setNumOfChildren(2);
			Root->SetRight(NULL);
			return temp;
		}

		remove( node , node->getParent() );
		NumOfLeaf--;
		return temp;
	}
}

TreeNode *BTree::findKey(int k)
{
//	int tempKey;
//	TreeNode* temp = new TreeNode;
//	Worker* worker;
//
//	if(!Root)
//		return NULL;
//	temp=Root;
//	while(!temp->isLeaf())
//	{
//		if( *k < temp->GetMinM() )
//		{
//			temp=temp->GetLeft();
//			continue;
//		}
//		if( !temp->GetRight() || ( *k < temp->GetMinR() && temp->GetRight() ) )
//		{
//			temp=temp->GetMid();
//			continue;
//		}
//		temp=temp->GetRight();
//	}
//
//	if(temp)
//	{
//		worker = temp->GetData();
//		tempKey = worker->getKey();
//		if( *k == tempKey )
//			return temp;
//		else
//			return(NULL);
//	}
//	else
		return NULL;
}

void BTree::updateKeys( TreeNode* node )
{
	TreeNode* curr = node;

	while( curr->getParent() )
	{
		if( curr->GetMid() )
			curr->SetMinM( get_Lowest_Left_Key( curr->GetMid() ) );
		if( curr->GetRight() )
			curr->SetMinR( get_Lowest_Left_Key( curr->GetRight()) );
		else
			curr->SetMinR(NULL);

		curr = curr->getParent();
	}
	curr->SetMinM( get_Lowest_Left_Key( curr->GetMid() ) );
	if( curr->GetRight() )
		curr->SetMinR( get_Lowest_Left_Key( curr->GetRight() ) );
}
//simple cases of remove , non recursive
void BTree::basic_remove( TreeNode* node , TreeNode* parent , int childNum )
{
		switch(childNum)
		{
		case 1:
			{
				parent->SetLeft( parent->GetMid() );
				parent->SetMid( parent->GetRight() );
				break;
			}
		case 2:
			{
				parent->SetMid( parent->GetRight() );
				break;
			}
		default:
			{
				//3.right child // simple case 
				break;
			}
		}
		parent->setNumOfChildren( 2 );
		parent->setMinHolder( parent->GetMid()->getMinHolder() );
		parent->SetMinM( parent->GetMid()->GetMinM() );
		parent->SetMinR(NULL);
		updateKeys( parent );
		//parent->SetMinM( parent->GetMid()->getMinHolder() );
		parent->SetRight(NULL);
		
		return;
}
//remove handels with the case of deleting when a parent  has 2 children
void BTree:: remove( TreeNode* node , TreeNode* parent )
{
	/*================================================================*/
	//	 first time inside remove : node is the one to delete         //
	//	after recursive calls the node is the rest we want to keep!   // 
	/*================================================================*/

	int childNum; //1.left //2.middle //3.right
	childNum = Son_Location( parent , node );

	/*============ stop recursive ==============*/
	if( !parent->getParent() ) //we know when the node's parent is the root  , the parent of the root is NULL 
	{
		if( parent->getNumOfChildren() ==  1 ) 
			Root = node;
	
		if( parent->getNumOfChildren() ==  2 ) 
		{
			if(childNum == 2 )
			{
				Root->SetLeft( node );
				Root->SetMid( Root->GetRight() );
			}
		}

		return;
	}
	/*===============================================================*/
	if( parent->getNumOfChildren() == 3 )
	{
		basic_remove( node , parent , childNum );
		return;
	}
	/*======================================================================*/	
	if(parent->getNumOfChildren() <= 2 )
	{
		//forcing the remained node to be left
		if( childNum == 1 )
		{
			if(parent->GetMid())
				parent->SetLeft( parent->GetMid()  );
			parent->SetMid( NULL );
			node = parent->GetLeft();
		}
		if(childNum == 2)
		{
			parent->SetMid(NULL);
			node = parent->GetLeft();
		}
		
		//which child is the parent
		childNum = Son_Location( parent->getParent() , parent );

		//perent is left or right child
		if( childNum != 2 )
		{
			//simple cases of remove , non recursive
			if( parent->getParent()->GetMid()->getNumOfChildren() == 3 )
			{
				if( childNum == 1 ) 
				{
					parent->SetMid( parent->getParent()->GetMid()->GetLeft() );
					parent->getParent()->GetMid()->SetLeft( parent->getParent()->GetMid()->GetMid() );
					parent->getParent()->GetMid()->SetMid( parent->getParent()->GetMid()->GetRight() );
					parent->GetMid()->setParent( parent );
					parent->SetMinM( parent->GetLeft()->GetMinM() );
				}
				else
				{
					parent->SetMid( parent->GetLeft() );
					parent->SetLeft( parent->getParent()->GetMid()->GetRight() );
					parent->GetLeft()->setParent( parent ); 
				}
				parent->SetRight(NULL);
				parent->getParent()->GetMid()->SetRight( NULL );
				//re_arange keys
				parent->setMinHolder( parent->GetLeft()->GetMinM() );
				parent->SetMinR(NULL);
				parent->SetMinM( parent->GetMid()->GetMinM() );
				parent->getParent()->GetMid()->setNumOfChildren(2);
				updateKeys( parent );
				return;
			}
			else
			{
				add_node( node , parent->getParent()->GetMid() );
				if( childNum == 1 )
				{
					parent->getParent()->SetLeft( NULL );
					parent->getParent()->SetLeft( parent->getParent()->GetMid() );
					parent->getParent()->SetMid( parent->getParent()->GetRight() );
					parent->getParent()->SetRight(NULL);
				}
				if( childNum == 3 )
				{
					parent->getParent()->SetRight( NULL );
					parent->getParent()->SetMinR(NULL);
				}
				parent->getParent()->setNumOfChildren( parent->getParent()->getNumOfChildren()-1);
			}		
		}
		// parent is a middle child 
		if( childNum == 2) 
		{
			//simple cases of remove , non recursive
			if( parent->getParent()->GetLeft()->getNumOfChildren() == 3 )
			{
				parent->SetMid( parent->GetLeft() );
				parent->SetLeft( parent->getParent()->GetLeft()->GetRight() );
				parent->GetLeft()->setParent( parent );
				parent->getParent()->GetLeft()->SetRight(NULL);
				
				parent->setMinHolder( parent->GetLeft()->getMinHolder() );
				parent->SetMinM( parent->GetMid()->GetMinM() );
				parent->SetMinR(NULL);
				parent->getParent()->SetMinM( parent->getMinHolder() );
				parent->getParent()->GetLeft()->setNumOfChildren(2);
				updateKeys( parent );
				return;
			}
			//simple cases of remove , non recursive
			if( parent->getParent()->GetRight() )
				if( parent->getParent()->GetRight()->getNumOfChildren() == 3 )
				{
					parent->SetMid( parent->getParent()->GetRight()->GetLeft() );
					parent->getParent()->GetRight()->SetLeft( parent->getParent()->GetRight()->GetMid() );
					parent->getParent()->GetRight()->SetMid( parent->getParent()->GetRight()->GetRight() );
					parent->getParent()->GetRight()->SetRight(NULL);
					parent->GetMid()->setParent( parent );					
					
					parent->SetMinM( parent->GetMid()->getMinHolder() );
					parent->SetMinR(NULL);
					parent->getParent()->GetRight()->setNumOfChildren(2);					
					updateKeys( parent );
					return;
				}
				add_node( node , parent->getParent()->GetLeft() );
				parent->getParent()->SetMid( NULL );
				parent->getParent()->SetMid( parent->getParent()->GetRight() );
				parent->getParent()->SetRight(NULL);
				parent->getParent()->setNumOfChildren( parent->getParent()->getNumOfChildren()-1);
		}
	}

	
	if( node->getParent()->GetRight() )
		node->getParent()->SetMinR( node->getParent()->GetRight()->getMinHolder() );
	updateKeys( node->getParent() );
	//we get here to recursive call when there was no "causen to adopt" from the uncale
	remove( node->getParent() , node->getParent()->getParent() );
}


int BTree:: get_Lowest_Left_Key( TreeNode* node )
{
	TreeNode* curr = node; 
	if( !curr )
		return NULL;

	while( curr->GetLeft() )
	{
		curr = curr->GetLeft();
	}

	return curr->GetData()->getKey();
}
